package com.klun.likou;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution20 {

	public static void main(String[] args) {
		boolean valid = isValid("{}()[](((())){}[])");
		System.out.println(valid);
	}

	/**
	 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
	 * 有效字符串需满足：
	 * 左括号必须用相同类型的右括号闭合。
	 * 左括号必须以正确的顺序闭合。
	 * 注意空字符串可被认为是有效字符串。
	 */
	public static boolean isValid(String s) {
		// 辅助栈法
		Map<Character, Character> map = new HashMap();
		map.put(')', '(');
		map.put('}', '{');
		map.put(']', '[');
		Stack<Character> stack = new Stack<>();
		for (int i = 0, len = s.length(); i < len; i++) {
			Character character = map.get(s.charAt(i));
			if (null == character) {
				stack.push(s.charAt(i));
				continue;
			}
			if (!stack.pop().equals(character)) {
				return false;
			}
		}
		return stack.isEmpty();
	}
}